package com.demo.datastructure.linkedList;

import java.util.LinkedList;

/**
 * @description: 单项链表实现回文字符串
 * @author: ljr
 * @time: 2021/4/14 17:41
 */
public class LinkedListDemo {

    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
    }


    public boolean isPalindrome(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;


        while(fast == null || fast.next == null){
            fast = fast.next.next;
            ListNode next = slow.next;
            slow.next = prev;
            prev = slow;
            slow = next;
        }

        if(fast != null){
            slow = slow.next;
        }

        while (slow != null) {
            if (slow.val != prev.val) {
                return false;
            }
            slow = slow.next;
            prev = prev.next;
        }


        return true;
    }





    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
}



